package test;

import org.junit.Test;

import java.util.*;

/**
 * @Description 给定5个商品的价格，每个商品最多可以买2件，输出所有满足花费超过给定数字M的购买方案
 * @Author Firenut
 * @Date 2023-09-10 16:08
 */
public class OverTheM {
    List<List<Integer>> ans = new ArrayList<>();
    int maxPerProduct = 2;      // 每个商品最多购买数量
    int[] prices = {10, 20, 30, 40, 50}; // 商品价格
    int targetAmount = 100;     // 目标花费金额

    @Test
    public void test() {
        dfs(prices, new ArrayList<>(), 0, 0);
        ans.forEach(System.out::println);
    }

    void dfs(int[] price, List<Integer> temp, int index, int money) {
        // 拿到一个符合条件的记录
        if (money > targetAmount) {
            ans.add(new ArrayList<>(temp));
            // 这里不要return，还需要往下继续找
        }

        // 越界退出
        if (index >= price.length) {
            return;
        }

        // 选 0,1,2个
        for (int i = 0; i <= maxPerProduct; i++) {

            // 根据当前要选的个数，依次添加商品
            for (int j = 0; j < i; j++) {
                // 添加i个商品
                temp.add(index);
                money += price[index];
            }

            // 往下递归
            dfs(price, temp, index + 1, money);

            // 回溯
            for (int j = 0; j < i; j++) {
                temp.remove(temp.size() - 1);
                money -= price[index];
            }
        }
    }

//    public static void main(String[] args) {
//        int[] prices = {10, 20, 30, 40, 50}; // 商品价格
//        int maxPerProduct = 2; // 每个商品最多购买数量
//        int targetAmount = 100; // 目标花费金额
//
//        List<List<Integer>> result = findPurchaseOptions(prices, maxPerProduct, targetAmount);
//
//        if (result.isEmpty()) {
//            System.out.println("没有满足条件的购买方案。");
//        } else {
//            System.out.println("满足条件的购买方案如下：");
//            for (List<Integer> option : result) {
//                System.out.println(option);
//            }
//        }
//    }
//
//
//    public static List<List<Integer>> findPurchaseOptions(int[] prices, int maxPerProduct, int targetAmount) {
//        List<List<Integer>> result = new ArrayList<>();
//        List<Integer> currentOption = new ArrayList<>();
//        generatePurchaseOptions(prices, maxPerProduct, targetAmount, 0, currentOption, result);
//        return result;
//    }
//
//
//    /**
//     * @param prices 商品价格
//     * @param maxPerProduct 每个商品的最大数量
//     * @param remainingAmount 剩余商品的数量
//     * @param index 当前商品的编号
//     * @param currentOption 当前结果集
//     * @param result 所有组合答案
//     */
//    public static void generatePurchaseOptions(int[] prices, int maxPerProduct, int remainingAmount, int index,
//                                               List<Integer> currentOption, List<List<Integer>> result) {
//        if (remainingAmount == 0) {
//            result.add(new ArrayList<>(currentOption));
//            return;
//        }
//
//        if (remainingAmount < 0 || index == prices.length) {
//            result.add(new ArrayList<>(currentOption));
//            return;
//        }
//
//        for (int quantity = 0; quantity <= maxPerProduct; quantity++) {
//            for (int i = 0; i < quantity; i++) {
//                currentOption.add(prices[index]);
//            }
//
//            generatePurchaseOptions(prices, maxPerProduct, remainingAmount - quantity * prices[index], index + 1, currentOption, result);
//
//            for (int i = 0; i < quantity; i++) {
//                currentOption.remove(currentOption.size() - 1);
//            }
//        }
//    }
}
